#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2021/01/14
# @Author   :Changshu
# @File     :Exercise_669.py

# 669. 修剪二叉搜索树

# 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，
# 使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构
# （即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。
#
# 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

# Definition for a binary tree node.
class TreeNode:
	def __init__(self, val=0, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right


class Solution:
	def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
		if root is None:
			return root
		if root.val<low:
			return self.trimBST(root.right,low,high)
		if root.val>high:
			return self.trimBST(root.left,low,high)
		root.left=self.trimBST(root.left,low,high)
		root.right=self.trimBST(root.right,low,high)
		return root

	def inOrder(self,root: TreeNode):
		if root is None:
			print('None',end=' ')
		else:
			self.inOrder(root.left)
			print(root.val,end=' ')
			self.inOrder(root.right)

if __name__ == '__main__':
	solution=Solution()
	root=TreeNode(1)
	node2_1=TreeNode(0)
	node2_2=TreeNode(2)

	root.left=node2_1
	root.right=node2_2

	solution.inOrder(root)




